|
The Steinhaus–Johnson–Trotter algorithm or Johnson–Trotter algorithm, also called plain changes, is an algorithm named after Hugo Steinhaus, Selmer M. Johnson and Hale F. Trotter that generates all of the permutations of ''n'' elements. Each permutation in the sequence that it generates differs from the previous permutation by swapping two adjacent elements of the sequence. Equivalently, this algorithm finds a Hamiltonian path in the permutohedron. This method was known already to 17th-century English change ringers, and calls it "perhaps the most prominent permutation enumeration algorithm". As well as being simple and computationally efficient, it has the advantage that subsequent computations on the permutations that it generates may be sped up because these permutations are so similar to each other.〔.〕 ==Recursive structure== The sequence of permutations for a given number ''n'' can be formed from the sequence of permutations for ''n'' − 1 by placing the number ''n'' into each possible position in each of the shorter permutations. When the permutation on ''n'' − 1 items is an even permutation (as is true for the first, third, etc., permutations in the sequence) then the number ''n'' is placed in all possible positions in descending order, from ''n'' down to 1; when the permutation on ''n'' − 1 items is odd, the number ''n'' is placed in all the possible positions in ascending order.〔, section 3.〕 Thus, from the single permutation on one element, :1 one may place the number 2 in each possible position in descending order to form a list of two permutations on two elements, :1 2 :2 1 Then, one may place the number 3 in each of three different positions for these three permutations, in descending order for the first permutation 1 2, and then in ascending order for the permutation 2 1: :1 2 3 :1 3 2 :3 1 2 :3 2 1 :2 3 1 :2 1 3 At the next level of recursion, the number 4 would be placed in descending order into , in ascending order into , in descending order into , etc. The same placement pattern, alternating between descending and ascending placements of ''n'', applies for any larger value of ''n''. In this way, each permutation differs from the previous one either by the single-position-at-a-time motion of ''n'', or by a change of two smaller numbers inherited from the previous sequence of shorter permutations. In either case this difference is just the transposition of two adjacent elements. When the first and final elements of the sequence, also, differ in only two adjacent elements (the positions of the numbers 1 and 2), as may be shown by induction. Although this sequence may be generated by a recursive algorithm that constructs the sequence of smaller permutations and then performs all possible insertions of the largest number into the recursively-generated sequence, the actual Steinhaus–Johnson–Trotter algorithm avoids recursion, instead computing the same sequence of permutations by an iterative method. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Steinhaus–Johnson–Trotter algorithm」の詳細全文を読む スポンサード リンク
|